package day_2022_4_to_7.nowcoder;

import java.util.Stack;

/**
 * 二叉搜索树的第k个节点 && 剑指 Offer 54.二叉搜索树的第k大节点
 *
 * 给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三
 * 小结点的值为4。
 * @author haomin
 * @date 2022/05/13 17:17
 **/
public class KthNode_35 {
    TreeNode KthNode(TreeNode pRoot, int k){
        if(pRoot == null || k <= 0){
            return null;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = pRoot;
        while (cur != null || !stack.isEmpty()){
            while (cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            if(!stack.isEmpty()){
                cur = stack.pop();
                k--;
                if(k == 0){
                    return cur;
                }
            }
            cur = cur.right;
        }
        return null;
    }
}